11. Container With Most Water

Posted on | In

11. Container With Most Water

Description

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

question_11

解答

这道题最简单的解法是用暴力破解，即遍历每对可能的边，计算可以容纳水的体积，但是这样的复杂度为O($n^2$)。

一种更简单的方法使用两个指针的方法，一个指针指向数组的头部，另一个指向数组的尾部，计算两条边之间可以容纳水的体积，然后比较头指针指向的边和尾指针指向的边的长度，如果头指针指向的边长，就令尾指针 -1 ，否则头指针 +1。

在这个过程中，我们定义一个变量MostWater，实施更新可以容纳的最大体积。
时间复杂度为O($n$)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxArea(vector<int>& height) {
        int lo = 0;
        int hi = height.size() - 1;
        int MostWater = 0;
        while (lo < hi) {
        	MostWater = max(MostWater, (hi - lo) * min(height[lo], height[hi]));
        	if (height[lo] > height[hi])
        		hi --;
        	else lo ++;

        }
        return MostWater;

    }